package com.shuang.string6;

public class StrStr {

    public int strStr(String haystack, String needle) {
        //KMP算法 前缀表 不减一不移位
        //前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配
        //主串一直在往前走 模式串与主串不匹配模式串要退回
        // 数组next代表前缀表 next[i]表示前i位（包括i）的字符构成的字符子串的前缀和后缀相等的最大长度 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串，后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

        if (needle.length() == 0){
            return 0;
        }

        //得到next数组
        int[] next = getNext(needle);

        //模式串的索引 根据条件要退回的
        int j = 0;

        //主串一直在走
        for (int i = 0; i < haystack.length(); i++) {

            //匹配冲突的情况 j退回到 next[j-1] 的索引位置
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)){
                j = next[j - 1];
            }

            //匹配上了就正常往后走
            if (haystack.charAt(i) == needle.charAt(j)){
                j++;
            }

            //找到了 返回第一个匹配项的索引
            if (j == needle.length()){
                return i - j + 1;
            }
        }

        //没找到返回-1
        return -1;
    }

    //计算前缀表 next数组
    public int[] getNext(String s){
        int len = s.length();
        int[] next = new int[len];

        //初始化next数组
        next[0] = 0;

        //要回退索引 也是前缀后缀相等时的最大长度 next数组要取的值
        int j = 0;

        //相当于在一个字符串中 将i的位置当成主串最后一个字符 j当成模式串最后一个字符 j是要退回的 i是一直向前走的
        for (int i = 1; i < s.length() - 1; i++){

            //匹配冲突
            while (j > 0 && s.charAt(i) != s.charAt(j)){
                j = next[j - 1];
            }

            //匹配成功
            if (s.charAt(i) == s.charAt(j)){
                j++;
            }

            //j 也是next数组要取的值
            next[i] = j;
        }
        return next;
    }
}
